#include<iostream>
#include<string>
#include<stdlib.h>
using namespace std;

typedef struct LNode
{
	int digit;
	struct LNode *next;
}tLNode;

//tLNode *L1,*L2;

void 
createList(tLNode *head,int array[],int n)
{
	head = new tLNode();
	head->next = NULL;
	for(int i=0;i<n;i++)
	{
		addNode(head,array[i]);
	}

}

void 
addNode(tLNode* p,int val)
{
	tLNode *s = new tLNode();
	while(p->next!=NULL)
	{
		p=p->next;
	}
	s->digit = val;
	s->next = NULL;
	p->next = s;
}

tLNode* sumList(tLNode *l1,tLNode *l2)
{
	tLNode *head = new tLNode();
	head->next = NULL;

	while(l1->next!=NULL && l2->next!=NULL)
	{
		l1=l1->next; l2=l2->next;
		int gewei,shiwei;
		if ( (l1->digit+l2->digit)<10 )
		{
			gewei=(l1->digit+l2->digit);
			hiwei=0 ;
		}
		else	
		{
			gewei=(l1->digit+l2->digit)%10;
			shiwei=(l1->digit+l2->digit)/10;
		}

		if(l1->next!=NULL)		//whether to the end of the list
			l1->next->digit += shiwei;
		else if(l2->next!=NULL)
			l2->next->digit += shiwei;
		else 
		{
			addNode(head,shiwei);
			break;
		}
		addNode(head,gewei);
	}	

	if(l1->next == NULL && l2->next == NULL)
	{
		return head;
	}
	else if(l1->next == NULL)
	{
		while(l2->next!=NULL)
		{
			l2=l2->next;
			
		}
	}
	else (l2->next == NULL)
	{
	
	}
}

void display(tLNode *p)
{
	while(p->next!=NULL)
	{
		p=p->next;
		cout<<p->digit<<" ";
	}
	cout<<endl;
}

int 
main()
{
	int a1[]={3,1,5};
	int a2[]={5,9,2};
	int b1[]={2,8,8};
	int b2[]={9,5,5,9};
	
	tLNode *La1,*La2,*Lb1,*Lb2;
	createList(La1,a1,sizeof(a1)/sizeof(a1[0]));
	createList(La2,a2,sizeof(a2)/sizeof(a2[0]));
	createList(Lb1,b1,sizeof(b1)/sizeof(b1[0]));
	createList(Lb1,b2,sizeof(b2)/sizeof(b2[0]));
	
	tLNode *p = sumList(La1,La2);
	display(p);

	p = sumList(Lb1,Lb2);
	display(p);

	return 0;
}
